1. Field of the Invention
The invention relates to the field of signal encoding, and in particular, to a signal encoding method and apparatus useful for digital watermarking, encryption, and the like.
2. Background Information
With the advent of computer networks and digital multimedia, protection of intellectual property has become a prime concern for creators and publishers of digitized copies of copyrightable works, such as musical recordings, movies, and video games.
What differentiates the “digital marketplace” from the physical marketplace is the absence of a widely accepted scheme that establishes responsibility and trust in the authenticity of goods. For physical products, corporations and governments mark the goods and monitor manufacturing capacity and sales to estimate loss from piracy. There also exist reinforcing mechanisms, including legal, electronic, and informational campaigns to better educate consumers.
One method of protecting copyrights in the digital domain is to use “digital watermarks”. Digital watermarks can be used to mark each individual copy of a digitized work with information identifying the title, copyright holder, and even the licensed owner of a particular copy.
Digital watermarks provide creators and publishers of digitized multimedia content localized, secured identification and authentication of that content. The problem of piracy is clearly a disincentive to the digital distribution of copyrighted works. The establishment of responsibility for copies and derivative copies of such works is invaluable. In considering the various forms of multimedia content, whether “master,” stereo, NTSC video, audio tape or compact disc, tolerance of quality degradation will vary with individuals and affect the underlying commercial and aesthetic value of the content.
The watermarks can serve to allow for secured metering and support of other distribution systems of given media content and relevant information associated with them, including addresses, protocols, billing, pricing or distribution path parameters, among the many things that could constitute a “watermark.” When marked with licensing and ownership information, responsibility is created for individual copies where before there was none.
Digital watermarks can be encoded with random or pseudo random keys, which act as secret maps for locating the watermarks. These keys make it impossible for a party without the key to find the watermark—in addition, the encoding method can be enhanced to force a party to cause damage to a watermarked data stream when trying to erase a random-key watermark.
U.S. Pat. No. 5,822,432 (Moskowitz et al.) issued Oct. 13, 1998, “Method for human-assisted random key generation and application for digital watermark system” discloses (paraphrasing the Abstract) a method for the human-assisted generation and application of pseudo-random keys for the purpose of encoding and decoding digital watermarks to and from a digitized data stream. A pseudo-random key and key application “envelope” are generated and stored using guideline parameters input by a human engineer interacting with a graphical representation of the digitized data stream. Key “envelope” information is permanently associated with the pseudo-random binary string comprising the key. Key and “envelope” information are then applied in a digital watermark system to the encoding and decoding of digital watermarks. Improvements to the methods of encoding and decoding digital watermarks are disclosed: separation of the encoder from the decoder, increased information capacity relative to spread spectrum methods, destruction of content resulting from attempts to erase watermarks, detection of presence of watermarks without ability to access watermark information, multi-channel watermark capability, use of various classes of keys for watermark access control, support for alternative encoding, decoding, or other component algorithms, use of digital notary to authenticate and time stamp watermark certificates.
U.S. Pat. No. 5,889,868 (Moskowitz et al.) dated Mar. 30, 1999 “Optimization methods for the insertion, protection, and detection of digital watermarks in digitized data” discloses (paraphrasing the Abstract) implementations of digital watermarks to various transmission, distribution and storage mediums taking into consideration the nature of digitally-sampled audio, video and other multimedia works. Watermark application parameters are adapted to the individual characteristics of a given digital sample stream. Watermark information is either carried in individual samples or in relationships between multiple samples, such as in a waveform shape. More optimal models are obtained to design watermark systems that are tamper-resistant given the number and breadth of existent digitized sample options with different frequency and time components. Quality of a given content signal may be maintained as it is mastered, with the watermark suitably hidden, taking into account usage of digital filters and error correction. The quality of the underlying content signals can be used to identify and highlight advantageous locations for the insertion of digital watermarks. The watermark is integrated as closely as possible to the content signal, at a maximum level to force degradation of the content signal when attempts are made to remove the watermarks.
Some methods that could be used for digital watermarking include amplitude or phase encoding or data encryption. However, for amplitude encoding, it is difficult to preserve a signal's characteristics and yet have a robust scheme that would not alter the signal envelope to the point that the watermark would distort the signal in a noticeable way. Phase encoding of a watermark would also destroy the fidelity of video and audio signals and could easily be detected (as could amplitude encoding).
A watermark could be included by signal encryption, but the encryption and decryption process are time consuming for larger data blocks and requires more expensive hardware.
Therefore, a need exists for a watermarking method and apparatus that overcomes the limitations and problems noted above.
It is known to generate a binary sequence for scrambling distributed samples and sampling the sequence at non-uniform sampling time intervals, descrambling using a comparator. For example, U.S. Pat. No. 5,245,661 (Lee et al.) issued Sep. 14, 1993, discloses (Abstract) a distributed sample scrambling system comprising scrambler and a descrambler. The scrambler includes a first shift register generator for generating a scrambler sequence, an exclusive OR gate for generating a scrambled bit stream by adding the binary sequence to a scrambler input bit stream, and a first sampling unit for sampling the scrambler sequence at non-uniform sampling intervals. The descrambler includes a second shift register generator for generating a descrambler sequence, a second sampling unit for sampling the descrambler sequence at the same sampling times, a comparator for comparing the samples of the descrambler sequence to the samples of the scrambler sequence in order to determine whether the samples of both the descrambler and the scrambler are identical, a correction circuit for outputting correction signals corresponding to the comparison results of the comparator to the second shift register generator, and an exclusive OR gate for generating a descrambled bit stream by adding the descrambler sequence to the scrambled bit stream of the scrambler.
It is also known to scramble an input speech signal via an analog-to-digital converter which samples it at the Nyquist rate. For example, U.S. Pat. No. 4,773,092 (Huang) issued Sep. 20, 1988, discloses (Abstract) a band scrambler which processes only time domain samples is described. The band scrambler has the effect of dividing the input signal spectrum into N sub-bands. The N sub-bands are permuted such that the r th band is mapped onto the k.r th band modulo N, where N is a constant of the scrambler and k is the key which is variable in the range 2<k<N−1.
In “The Shannon Sampling Theorem—Its Various Extensions and Applications: A Tutorial Review” (Abdul J. Jerri, Proc. Of the IEEE, Vol. 65, No. 11, November 1977, pages 1565 to 1598) at page 1575, mention is made of the so-called “folk-theorem” relating to sampling. Briefly, the folk-theorem states that any analog signal can be sampled with a non-uniform (or uneven) sampling period without losing content or risking aliasing, as long as the average sampling frequency exceeds the Nyquist rate, i.e., the number of samples per unit time is at least twice the highest frequency present in the analog signal being sampled. For example, CD-quality audio signals are typically sampled at 44,100 Hz. According to the theorem, an uneven sampling period must be no greater than about 23 microseconds on the average in order to retain content and avoid aliasing, assuming the highest frequencies in the audio signal are below 22,050 Hz, i.e., the upper end of the range of audible frequencies. Therefore, according to the theorem, it is possible to digitize an analog signal at an uneven rate, or to resample an existing digital signal at an uneven rate, without losing information content or risking aliasing if the criterion of the folk theorem is met. However, approximately 99.999% of digital signal processing (DSP) applications, textbooks, and devices rely on a fixed sampling period. When the sampling period is not fixed, the textbook methods for estimating frequency spectrums, filtering, etc., are incorrect.